package PersonStu.sanqi;

import java.util.HashMap;

/**
 * @Author: Dijah
 * @Date: 2022/10/27 16:35
 * @Desc:
 * 构造一个TopRecord
 *
 * TopRecord{
 *     public TopRecord(int k) : 构造时事先指定好k的大小，构造后 就固定不变了
 *     pulic void add(string str) : 向该结构中加入一个字符串，可以重复加入
 *     pulic List<string> top() : 返回之前加入的所有字符串中，词频最大的k个
 * }
 *
 * 要求：
 * add方法，复杂度O(logk)
 * top方法，复杂度O(K)
 *
 * 使用小根堆
 */
public class code_07_TopKTimesRealTime {

    public static class Node{

        public String str;
        public int times;

        public Node(String str, int times) {
            this.str = str;
            this.times = times;
        }
    }

    public static class TopKRecord{
        private Node[] heap;
        private int heapSize;
        //k-v str 和 times 的map
        private HashMap<String,Node> strNodeMap;
        // v => 词频
        private HashMap<Node,Integer> nodeIndexMap;

        //初始化
        public TopKRecord(int k) {
            heap = new Node[k];
            heapSize = k;
            strNodeMap = new HashMap<String,Node>();
            nodeIndexMap = new HashMap<Node,Integer>();
        }

        public void add(String str){
            Node curNode = null ;
            int preIndex = -1;// str之前在堆上的位置
            //查询词频，看有没有str的记录
            if(!strNodeMap.containsKey(str)){
                //str之前没有进来过
                curNode = new Node(str,1);
                //没有进来过，就放到strNodeMap 和 nodeIndexMap
                strNodeMap.put(str,curNode);
                nodeIndexMap.put(curNode,-1);
            }else{
                // str之前进来过
                curNode = strNodeMap.get(str);
                //次数++
                curNode.times++;
                preIndex = nodeIndexMap.get(curNode);
            }

            //词频修改完毕之后，
            //这里注意，只有在 strNodeMap 中 没有进来过的才是-1
            if(preIndex == -1){
                //说明不在堆上

                //如果堆满了
                if(heapSize == heap.length){
                    //堆满了，就比较头
                    if(heap[0].times < curNode.times){
                        //这里是小根堆，如果堆顶的times小于当前操作的times.那么就进来
                        nodeIndexMap.put(heap[0],-1); // 赋值一个-1，表示断开

                        nodeIndexMap.put(curNode,0);
                        heap[0] = curNode;//当做头
                        heapify(0,heapSize);
                    }

                }else{
                    //堆没有满,放到堆中

                    //没有满的话，就将当前的这个节点放到堆的最后的节点
                    nodeIndexMap.put(curNode,heapSize);
                    heap[heapSize] = curNode;

                    //你把当前的节点放到堆里面了，你给我往上pk去吧，我用的是小根堆，所以向上pk去吧
                    heapInsert(heapSize++);
                }
            }else{
                //在堆上，直接 heapify
                heapify(preIndex,heapSize);
            }
        }

        private void heapInsert(int index) {
            while (index != 0){
                //找到父节点
                int parent = (index - 1)/2;
                if(heap[index].times < heap[parent].times){
                    // 如果当前要插入的节点 小于 父节点
                    swap(parent,index);
                    index = parent;
                }else{
                    break;
                }
            }
        }

        private void heapify(int index, int heapSize) {
            //左孩子
            int left = index * 2 + 1;
            //右孩子
            int right = index * 2 + 2;
            //定义一个最小的
            int smallest = index;
            while (left < heapSize){
                //把heap中小的那值给smallest ,左孩子或者右孩子
                if(heap[left].times < heap[index].times){
                    left = smallest;
                }
                if(right < heapSize && heap[right].times < heap[smallest].times){
                    right = smallest;
                }
                if(smallest != index){
                    swap(smallest,index);
                }else{
                    break;
                }
                index = smallest;
                left = index * 2 + 1;
                right = index * 2 + 2;
            }

        }

        private void swap(int index1, int index2) {
            nodeIndexMap.put(heap[index1],index2);
            nodeIndexMap.put(heap[index2],index1);
            Node temp = heap[index1];
            //交换节点
            heap[index1] = heap[index2];
            heap[index2] = temp;
        }

        public void printTopK(int index){
            for (int i = 0; i < heap.length; i++) {
                if(heap[i] == null){
                    break;
                }
                System.out.print("str:"+heap[i].str);
                System.out.println("times:"+heap[i].times);
            }
        }


    }

}
